package jago02.jago0201.ag01_sort;

import java.util.Arrays;

/**
 * 希尔排序
 * 杂化简：插入排序的升级版本，预设一个步幅h，并动态调整步幅h，将数组分为h个组，然后每个组之间进行插入排序
 * 解目录：
 *      0.将数组分为步幅h把数组分为h个子数组，每个子数组又分为有序数组和无序数组，左边为有序数组，右边为无序数组
 *      1.h个子数组分别是[0,h,2h,3h..],[1,h+1,2h+1,3h+1]，默认最左侧为有序数组，分别将每个子数组中无序部分的元素插入排序到各自的有序部分
 * 复杂度：O(NLogN)
 */
public class Sort04_Shell {
    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,8,0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(Comparable[] arr) {
        //获取步幅
        int h = 1;
        while (h<arr.length/2){
            h = 2*h+1;
        }
        //根据步幅，动态变化步幅，反复进行排序
        while (h>=1){
            for (int i = h; i < arr.length ; i++) {
                //在步幅范围内比较元素
                for (int j = i; j >=h ; j-=h) {
                    if (bigThan(arr[j-h],arr[j])){
                        exch(arr,j-h,j);
                    }else{
                        break;
                    }
                }
            }
            h=h/2;
        }

    }

    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean bigThan(Comparable m, Comparable n) {
       return m.compareTo(n)>0;
    }
}
